package com.major.dawn.leetCode.array;

import java.util.HashMap;
import java.util.Set;

public class NumberArrayUntil {


    //    hashMap 算是一种比较常见思想了，这里我一开始还比较困惑，int数组的取值范围，用hashMap就可以自己去实现了
//    如何找出那些出现在第一个数组中，但是没有出现在第二个数组中的数字？
    public Integer[] differentSet(Integer[] nums1, Integer[] nums2) {
        HashMap<Integer, Integer> integerHashMap = new HashMap<>();
        int length1 = nums1.length;
        int length2 = nums2.length;
        if (length2 == 0 || length1 == 0) {

            return nums1;
        }
        for (int i = 0; i < length1; i++) {
            integerHashMap.put(nums1[i], 1);
        }

        for (int i = 0; i < length2; i++) {
            int key = nums2[i];
            Integer value = integerHashMap.get(key);
            if (value != null) {
                integerHashMap.remove(key);
            }
        }

        Set<Integer> integers = integerHashMap.keySet();

        return integers.toArray(new Integer[integers.size()]);


    }

    //   给定两个数组，编写一个函数来计算它们的交集。
//    先排序在双指针实现
    public int[] intersect(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        if (length1 == 0 || length2 == 0) {
            return new int[0];
        }

//        从小到大
        int[] sortNums1 = mergeSort(nums1);
        int[] sortNums2 = mergeSort(nums2);

        int intersectLength = 0;

        int i = 0;
        int j = 0;
        while (i < length1 && j < length2) {
            if (sortNums1[i] == sortNums2[j]) {
                sortNums1[intersectLength] = sortNums2[j];
                intersectLength++;
                i++;
                j++;
                continue;
            }
            if (sortNums1[i] < sortNums2[j]) {
                i++;
                continue;
            }

            if (sortNums1[i] > sortNums2[j]) {
                j++;
            }
        }
        int[] dest = new int[intersectLength];
        if (intersectLength == 0) {
            return dest;
        }

        System.arraycopy(sortNums1, 0, dest, 0, intersectLength);
        return dest;

    }

//    并归排序，分而治之的思想
    private int[] mergeSort(int[] nums) {
        int[] fork = fork(nums, 0, nums.length);

        return fork;
    }

    public int[] fork(int[] nums, int start, int size) {
        if (size > 2) {
            int middle= size / 2;
            int[] fork1 = fork(nums, start, middle);
            int[] fork2 = fork(nums, start + middle, size - middle);
            int joinLength = fork1.length + fork2.length;
            int[] join = new int[joinLength];

            int i =0;int j = 0;int index = 0;
            while (i < fork1.length && j < fork2.length) {
                if (fork1[i] < fork2[j]) {
                    join[index] = fork1[i];
                    i++;
                } else {
                    join[index] = fork2[j];
                    j++;
                }
                index++;
            }

            if (index == joinLength) {
                return join;
            }

            if (j == fork2.length) {
                System.arraycopy(fork1, i, join, index, joinLength - index);
            }else {
                System.arraycopy(fork2, j, join, index, joinLength - index);
            }
            return join;

        }

        if (size == 1) {
            return new int[]{nums[start]};
        }

        if (size == 2) {
            if (nums[start] <= nums[start + 1]) {
                return new int[]{nums[start], nums[start + 1]};
            }else {
                return new int[]{nums[start+1],nums[start]};
            }
        }

        return null;// 不会发生
    }


    public static void main(String[] args) {
        NumberArrayUntil numberArrayUntil = new NumberArrayUntil();
        Integer[] integers = numberArrayUntil.differentSet(new Integer[]{1, 2, 8, 8, 3}, new Integer[]{3, 5});
        for (int i = 0; i < integers.length; i++) {
            System.out.println(integers[i]);
        }


        int[] ints = numberArrayUntil.mergeSort(new int[]{1, 2, 8, 8, 3});
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }

    }


}
